package exampleQuestions;


public class BalancedBSTFromArray {
	
	static class Node {
		int val;
		Node left, right;
		
		Node(int v) {
			this.val = v;
		}
	}

	/**
	 * What's the best way to create a balanced binary search tree from a sorted
	 * singly linked list?
	 */
	public static void main(String[] args) {

		int array[] = new int[]{3, 5, 6, 9, 13, 14, 20, 21, 24};
		
		Node root = createBST(array, 0, array.length-1);
		
		printTree(root);
		
		System.out.println();
		System.out.println(root.val);
		System.out.println(root.left.val);
		System.out.println(root.right.val);
	}

	private static void printTree(Node root) {
		if (root != null) {
			printTree(root.left);
			System.out.print(root.val + " ");
			printTree(root.right);
		}
	}

	private static Node createBST(int[] array, int i, int j) {
		
		if (i<=j) {
			int mid = (i+j) >> 1;
			Node n = new Node(array[mid]);
			n.left = createBST(array, i, mid-1);
			n.right = createBST(array, mid+1, j);
			
			return n;
		} else {
			return null;
		}
	}

}